#include <gtest/gtest.h>

using namespace ::std;

// 解法汇总
// 纵向扫描
// 横向扫描
// 分治法
// 二分查找
// 先排序，后比较头尾
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs);
    // int getMinLenOfStrings(vector<string>& strs);
};

string Solution::longestCommonPrefix(vector<string>& strs) {
    for(int i = 0; i < strs[0].size(); ++i) {
        char c = strs[0][i];
        for(int j = 0; j < strs.size(); ++j) {
            if(c != strs[j][i]) return strs[0].substr(0, i);
        }
    }
    return strs[0];
}

// v01
// string Solution::longestCommonPrefix(vector<string>& strs) {
//     string result = "";
//     int minLenOfString = getMinLenOfStrings(s);
//     int i, j;
//     for(i = 0; i < minLenOfString; ++i) {
//         char c = strs[0][i];
//         for(j = 0; j < strs.size() && c == strs[j][i]; ++j)
//             ;
//         if(j < strs.size()) break;
//         result += c;
//     }
//     return result;
// }

// int Solution::getMinLenOfStrings(vector<string>& strs) {
//     int minLenOfString = strs[0].size();
//     for(int i = 1; i < strs.size(); ++i) {
//         if(minLenOfString > strs[i].size()) {
//             minLenOfString = strs[i].size();
//         }
//     }
//     return minLenOfString;
// }

class LongestCommonPrefixCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(LongestCommonPrefixCheck, testLongestCommonPrefix_1) {
    vector<string> strs = {"flower","flow","flight"};
    EXPECT_TRUE("fl" == solution.longestCommonPrefix(strs));
}

TEST_F(LongestCommonPrefixCheck, testLongestCommonPrefix_2) {
    vector<string> strs = {"dog","racecar","car"};
    EXPECT_TRUE("" == solution.longestCommonPrefix(strs));
}

TEST_F(LongestCommonPrefixCheck, testLongestCommonPrefix_3) {
    vector<string> strs = {"flower","f","f"};
    EXPECT_TRUE("f" == solution.longestCommonPrefix(strs));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
